#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

const int INF = INT_MAX;
void dijkstra(int v0, int n, vector<vector<int>>& graph)
{
	vector<int> dist(n, INF);
	dist[v0] = 0;
	vector<bool>visited(n, false);
	for (int i = 0; i < n; i++)
	{
		int u = -1;
		for (int j = 0; j < n; j++)
		{
			if (!visited[j] && (u == -1 || dist[j] < dist[u]))
			{
				u = j;
			}
		}
		visited[u] = true;

		for (int v = 0; v < n; ++v)
		{
			if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v])
			{
				dist[v] = dist[u] + graph[u][v];
			}
		}
		
	}
	cout << dist[n - 1];
}

void test3()
{
	int n, m, u, v, w;
	cin >> n >> m;
	vector<vector<int>> graph(n, vector<int>(n,INF));
	for (int i = 0; i < m; ++i)
	{
		cin >> u >> v >> w;
		if (w < graph[u - 1][v - 1])
		{
			graph[u - 1][v - 1] = w;
			graph[v - 1][u - 1] = w;
		}
	}
	dijkstra(0, n, graph);
}

int main()
{
	test3();
	return 0;
}